//https://leetcode.cn/problems/minimum-time-to-collect-all-apples-in-a-tree/submissions/589198833/
class Solution {
public:
    int dfs(int curn, vector<vector<int> >& g, vector<bool>& vis, vector<bool>& hasApple, int cost)
    {
        if (vis[curn])
            return 0;
        vis[curn] = true;
        int childcost = 0;
        for (auto next : g[curn])
        {
            childcost += dfs(next, g, vis, hasApple, 2);
        }
        if (!hasApple[curn] && childcost == 0)
            return 0;
        return childcost + cost;
    }
    int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
        vector<vector<int> > g(n);
        vector<bool> vis(n, false);

        for (auto edge : edges)
        {
            g[edge[0]].push_back(edge[1]);
            g[edge[1]].push_back(edge[0]);
        }
        return dfs(0, g, vis, hasApple, 0);
    }

};
